package offer.linkedList;

/**
 * @author DengYuan2
 * @create 2021-02-22 19:19
 */
public class n_22 {
    public static void main(String[] args) {
        n_22 n = new n_22();
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        ListNode n7 = new ListNode(7);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
//        n5.next = n6;
//        n6.next = n7;
        ListNode listNode = n.FindKthToTail2(n1, 6);
        System.out.println(listNode);
    }

    /**
     * 我的写法：先遍历得到总个数，再从前开始往后数n-k个
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode node = head;
        int count = 0;
        while (node != null) {
            count++;
            node = node.next;
        }
        int toFind = count - k + 1;
        if (toFind < 1) {
            return null;
        }
        node = head;
        for (int i = 1; i < toFind; i++) {
            node = node.next;
        }
        return node;
    }


    /**
     * 大神-双指针
     * 思想：设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，
     * 则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道
     * 当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是
     * 倒数第 K 个节点。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail2(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        //注意这两个判断的顺序不能调换哦，否则 {1,2,3,4,5},6 这个测试用例会出错啊
        while (fast != null && k-- > 0) {
            fast = fast.next;
        }
        //当K>N时
        if (k>0){
            return null;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
